package CodeTop.最长回文子串;

// https://leetcode.cn/problems/longest-palindromic-substring/
// 中心扩散
class Solution {
    String res = "";

    public String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            helper(s, i, i); // 处理奇数长度的回文串
            helper(s, i, i + 1); // 处理偶数长度的回文串
        }
        return res;
    }

    void helper(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            String t = s.substring(l, r + 1);
            if (t.length() > res.length()) res = t;
            l--;
            r++;
        }
    }
}

// 动态规划
class Solution1 {
    public String longestPalindrome(String s) {
        // dp[i][j] s[i..j] 的子串是否是回文子串
        boolean[][] dp = new boolean[s.length()][s.length()];
        int l = 0, r = 0; // 记录结果的截取位置
        for (int i = s.length() - 1; i >= 0; i--)
            for (int j = i; j < s.length(); j++)
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                        dp[i][j] = true;
                        if (r - l < j - i) {
                            l = i;
                            r = j;
                        }
                }
        return s.substring(l, r + 1);
    }
}